The incidence game chromatic number of paths and subgraphs of wheels

The incidence game chromatic number was introduced to unify the ideas of the incidence coloring number and the game chromatic number. We determine the exact incidence game chromatic number of large paths and give a correct proof of a result stated by Andres [S.D. Andres, The incidence game chromatic number, Discrete Appl. Math. 157 (2009) 1980-1987] concerning the exact incidence game chromatic number of large wheels.     

On the locating chromatic number of Kneser graphs

Let c be a proper k-coloring of a connected graph G and Π=(C₁,C₂,…,C_k) be an ordered partition of V(G) into the resulting color classes. For a vertex v of G, the color code of v with respect to Π is defined to be the ordered k-tuple c_Π(v):=(d(v,C₁),d(v,C₂),…,d(v,C_k)), where d(v,C_i)=min{d(v,x)|x∈C_i},1≤i≤k. If distinct vertices have distinct color codes, then c is called a locating coloring. The minimum number of colors needed in a locating coloring of G is the locating chromatic number of G, denoted by χ_L(G). In this paper, we study the locating chromatic number of Kneser graphs. First, among some other results, we show that χ_L(KG(n,2))=n−1 for all n≥5. Then, we prove that χ_L(KG(n,k))≤n−1, when n≥k². Moreover, we present some bounds for the locating chromatic number of odd graphs.     

Three new upper bounds on the chromatic number

This paper introduces three new upper bounds on the chromatic number, without making any assumptions on the graph structure. The first one, ξ, is based on the number of edges and nodes, and is to be applied to any connected component of the graph, whereas ζ and η are based on the degree of the nodes in the graph. The computation complexity of the three-bound computation is assessed. Theoretical and computational comparisons are also made with five well-known bounds from the literature, which demonstrate the superiority of the new upper bounds.     

A structural theorem for planar graphs with some applications

In this note, we prove a structural theorem for planar graphs, namely that every planar graph has one of four possible configurations: (1) a vertex of degree 1, (2) intersecting triangles, (3) an edge xy with d(x)+d(y)≤9, (4) a 2-alternating cycle. Applying this theorem, new moderate results on edge choosability, total choosability, edge-partitions and linear arboricity of planar graphs are obtained.     

A branch-and-price approach for the partition coloring problem

This work proposes a new integer programming model for the partition coloring problem and a branch-and-price algorithm to solve it. Experiments are reported for random graphs and instances originating from routing and wavelength assignment problems arising in telecommunication network design. We show that our method largely outperforms previously existing approaches.     

The independence number of an edge‐chromatic critical graph

A graph G with maximum degree Δ and edge chromatic number χ′(G)>Δ is edge‐Δ‐critical if χ′(G?e)=Δ for every edge e of G. It is proved here that the vertex independence number of an edge‐Δ‐critical graph of order n is less than . For large Δ, this improves on the best bound previously known, which was roughly ; the bound conjectured by Vizing, which would be best possible, is . © 2010 Wiley Periodicals, Inc. J Graph Theory 66:98‐103, 2011     

Hitting all maximum cliques with a stable set using lopsided independent transversals

Rabern recently proved that any graph with contains a stable set meeting all maximum cliques. We strengthen this result, proving that such a stable set exists for any graph with . This is tight, i.e. the inequality in the statement must be strict. The proof relies on finding an independent transversal in a graph partitioned into vertex sets of unequal size. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:300‐305, 2011     

The number of defective colorings of graphs on surfaces

A (k, 1)‐coloring of a graph is a vertex‐coloring with k colors such that each vertex is permitted at most 1 neighbor of the same color. We show that every planar graph has at least cρⁿ distinct (4, 1)‐colorings, where c is constant and ρ≈1.466 satisfies ρ³ = ρ² + 1. On the other hand for any ε>0, we give examples of planar graphs with fewer than c(? + ε)ⁿ distinct (4, 1)‐colorings, where c is constant and . Let γ(S) denote the chromatic number of a surface S. For every surface S except the sphere, we show that there exists a constant c′ = c′(S)>0 such that every graph embeddable in S has at least c′2ⁿ distinct (γ(S), 1)‐colorings. © 2010 Wiley Periodicals, Inc. J Graph Theory 28:129‐136, 2011     

Clustering dynamics of nonlinear oscillator network: Application to graph coloring problem

The Kuramoto model is modified by introducing a negative coupling strength, which is a generalization of the original one. Among the abundant dynamics, the clustering phenomenon of the modified Kuramoto model is analyzed in detail. After clustering appears in a network of coupled oscillators, the nodes are split into several clusters by their phases, in which the phases difference within each cluster is less than a threshold and larger than a threshold between different clusters. We show that this interesting phenomenon can be applied to identify the complete sub-graphs and further applied to graph coloring problems. Simulations on test beds of graph coloring problems have illustrated and verified the scheme.     

On the oriented chromatic index of oriented graphs

A homomorphism from an oriented graph G to an oriented graph H is a mapping from the set of vertices of G to the set of vertices of H such that is an arc in H whenever is an arc in G. The oriented chromatic index of an oriented graph G is the minimum number of vertices in an oriented graph H such that there exists a homomorphism from the line digraph LD(G) of G to H (the line digraph LD(G) of G is given by V(LD(G)) = A(G) and whenever and ). We give upper bounds for the oriented chromatic index of graphs with bounded acyclic chromatic number, of planar graphs and of graphs with bounded degree. We also consider lower and upper bounds of oriented chromatic number in terms of oriented chromatic index. We finally prove that the problem of deciding whether an oriented graph has oriented chromatic index at most k is polynomial time solvable if k ≤ 3 and is NP‐complete if k ≥ 4. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 313–332, 2008